package medium

/*
时间复杂度:O(M*N)
空间复杂度:O(M*N)
*/

func uniquePaths(m int, n int) int {
	dp := make([][]int, m+1)
	dp[0] = make([]int, n+1)
	dp[0][1] = 1
	for i := 1; i <= m; i++ {
		dp[i] = make([]int, n+1)
		for j := 1; j <= n; j++ {
			dp[i][j] = dp[i-1][j] + dp[i][j-1]
		}
	}
	return dp[m][n]
}

/*
时间复杂度:O(M*N)
空间复杂度:O(N)
*/

func uniquePaths1(m int, n int) int {
	dp := make([]int, n+1)
	// 如果设置成dp[0]=1则最终结果就是dp[n-1]
	dp[1] = 1
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			dp[j] = dp[j] + dp[j-1]
		}
	}
	return dp[n]
}
